﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Trie
{
    public class Trie
    {
        private class Node
        {

            public bool isWord;
            public Dictionary<char, Node> next;

            public Node(bool isWord)
            {
                this.isWord = isWord;
                next = new Dictionary<char, Node>();
            }

            public Node() : this(false) { }
        }

        private Node root;
        private int size;

        public Trie()
        {
            root = new Node();
            size = 0;
        }

        // 获得Trie中存储的单词数量
        public int getSize()
        {
            return size;
        }

        // 向Trie中添加一个新的单词word
        public void add(string word)
        {

            Node cur = root;
            for (int i = 0; i < word.Length; i++)
            {
                char c = word.ElementAt(i);
                if (!cur.next.ContainsKey(c))
                    cur.next.Add(c, new Node());
                cur.next.TryGetValue(c, out cur);
            }

            if (!cur.isWord)
            {
                cur.isWord = true;
                size++;
            }
        }

        // 查询单词word是否在Trie中
        public bool contains(string word)
        {
            Node cur = root;
            for (int i = 0; i < word.Length; i++)
            {
                char c = word.ElementAt(i);
                if (!cur.next.ContainsKey(c))
                    return false;
                cur.next.TryGetValue(c, out cur);
            }
            return cur.isWord;
        }

        // 查询是否在Trie中有单词以prefix为前缀
        public bool isPrefix(String prefix)
        {

            Node cur = root;
            for (int i = 0; i < prefix.Length; i++)
            {
                char c = prefix.ElementAt(i);
                if (!cur.next.ContainsKey(c))
                    return false;
                cur.next.TryGetValue(c, out cur);
            }

            return true;
        }

    }
}
